﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Runtime.Serialization.Formatters.Binary;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Checkers
{
    class AI
    {
        internal bool selectRandomMove { get; set; }
        internal int aiDepth { get; set; }

        internal AI()
            : this(3)
        {
        }

        internal AI(int aiDepth)
        {
            this.selectRandomMove = false;
            this.aiDepth = aiDepth;
        }

        internal Task<CheckerPiece[,]> PerformAIMoveAsync(CheckerBoard checkerBoard, Player player)
        {
            return Task.Run(delegate
            {
                return PerformAIMove(checkerBoard, player); 
            });
        }

        internal CheckerPiece[,] PerformAIMove(CheckerBoard checkerBoard, Player player)
        {
            MiniMax ai = new MiniMax();

            if (player == Player.Black)
            {
                if (selectRandomMove)
                    return ai.NextRandomBlack(GetCheckerBoardInstance(checkerBoard));
                else
                    return ai.NextAIBlack(GetCheckerBoardInstance(checkerBoard));
            }
            else
            {
                if (selectRandomMove)
                    return ai.NextRandomRed(GetCheckerBoardInstance(checkerBoard));
                else
                    return ai.NextAIRed(GetCheckerBoardInstance(checkerBoard));
            }
        }

        internal CheckerPiece[,] GetCheckerBoardInstance(CheckerBoard checkerBoard)
        {
            return (CheckerPiece[,])checkerBoard.checkerBoard.Clone();
        }
    }

    //MiniMax Class
    //Implements the MiniMax Algorithm to find the next best move for Red(findMax) and Black(findMin)
    class MiniMax
    {
        //dlimit specifies the Depth Limit for how many iterations the MiniMax Algorithm goes.
        internal static int dlimit = 3;
        internal static Random rnd = new Random();

        internal MiniMax()
            : this(3)
        {
        }

        internal MiniMax(int dlimit)
        {
            MiniMax.dlimit = dlimit;
        }

        /*
         * NextRandomRed, NextRandomBlack, NextAIRed, NextAIBlack are interface methods to the other methods.
         * Use the right method based on the current player color.
         * Input - Current Gameboard
         * Output - Gameboard of the Computer's Next Move
         */
        internal CheckerPiece[,] NextRandomRed(CheckerPiece[,] gameboard)
        {
            AIMove root = new AIMove(gameboard);
            ArrayList redMoves = generateRedMoves(root.DeepClone(root));
            int rndIndex = rnd.Next(0, redMoves.Count);
            AIMove nextRedMove = (AIMove)redMoves[rndIndex];

            return nextRedMove.getboard();
        }

        internal CheckerPiece[,] NextRandomBlack(CheckerPiece[,] gameboard)
        {
            AIMove root = new AIMove(gameboard);
            ArrayList blackMoves = generateBlackMoves(root.DeepClone(root));
            int rndIndex = rnd.Next(0, blackMoves.Count);
            AIMove nextBlackMove = (AIMove)blackMoves[rndIndex];

            return nextBlackMove.getboard();
        }

        internal CheckerPiece[,] NextAIRed(CheckerPiece[,] gameboard)
        {
            AIMove root = new AIMove(gameboard);

            AIMove nextRedMove = findMax(root.DeepClone(root), 0);

            return nextRedMove.getboard();
        }

        internal CheckerPiece[,] NextAIBlack(CheckerPiece[,] gameboard)
        {
            AIMove root = new AIMove(gameboard);

            AIMove nextBlackMove = findMin(root.DeepClone(root), 0);

            return nextBlackMove.getboard();
        }

        /*
         * findMax method is used for the Red Player to find the next move.
         */
        internal AIMove findMax(AIMove root, int depth)
        {
            AIMove next = null;

            if (depth == dlimit)
            {
                return root;
            }
            else
            {
                AIMove best = null;
                ArrayList moves = new ArrayList();
                moves = generateRedMoves(root);

                for (int i = 0; i < moves.Count; i++)
                {

                    AIMove cand = findMin((AIMove)moves[i], depth + 1);

                    if (cand == null)
                    {
                    }
                    else if (best == null)
                    {
                        best = cand;
                    }
                    else if (cand.getPHV() > best.getPHV())
                    {
                        best = cand;
                    }
                    else if (cand.getPHV() == best.getPHV())
                    {
                        if (cand.getSRHV() > best.getSRHV())
                        {
                            best = cand;
                        }
                        else if (cand.getSRHV() == best.getSRHV())
                        {
                            if ((rnd.Next(0, 100) % 2) == 0)
                            {
                                best = cand;
                            }
                        }
                    }
                }
                if (depth == 0)
                {
                    next = best;
                }
                else
                {
                    next = root.DeepClone(root);
                    next.copyHValues(best);
                }
            }


            return next;
        }


        /*
         * findMin is used to find the Black Player's next move.
         */
        internal AIMove findMin(AIMove root, int depth)
        {
            AIMove next = null;

            if (depth == dlimit || root.getBlackPieces() == 0 || root.getRedPieces() == 0)
            {
                return root;
            }
            else
            {
                AIMove best = null;
                ArrayList moves = new ArrayList();
                moves = generateBlackMoves(root);

                for (int i = 0; i < moves.Count; i++)
                {
                    AIMove cand = findMax((AIMove)moves[i], depth + 1);

                    if (cand == null)
                    {
                    }
                    else if (best == null)
                    {
                        best = cand;
                    }
                    else if (cand.getPHV() < best.getPHV())
                    {
                        best = cand;
                    }
                    else if (cand.getPHV() == best.getPHV())
                    {
                        if (cand.getSBHV() > best.getSBHV())
                        {
                            best = cand;
                        }
                        else if (cand.getSBHV() == best.getSBHV())
                        {
                            if ((rnd.Next(0, 100) % 2) == 0)
                            {
                                best = cand;
                            }
                        }
                    }
                }
                if (depth == 0)
                {
                    next = best;
                }
                else
                {
                    next = root.DeepClone(root);
                    next.copyHValues(best);
                }
            }

            return next;
        }

        /*
         * Check Range Method - Ensures that the coordinates are within the boundary of the board.
         */
        internal Boolean checkRange(int i, int j)
        {
            Boolean movable = false;
            if (i < 8 && i >= 0 && j < 8 && j >= 0)
            {
                movable = true;
            }
            return movable;
        }

        /*
         * Check for Possible Checker Piece Jump AIMove
         * i,j is position for current piece
         * o,p is position for adjacent square
         * s,t is position for square where the piece would land if it is able to jump o,p
         */
        internal AIMove checkJump(AIMove root, CheckerPiece type, int i, int j, int o, int p, int s, int t)
        {
            CheckerPiece[,] board = root.getboard();
            AIMove jump = null;
            if (checkRange(s, t))
            {
                if (board[s, t] == 0)
                {
                    jump = new AIMove(root.DeepClone(root));
                    jump.edit(i, j, 0);
                    jump.edit(o, p, 0);
                    jump.edit(s, t, type);

                    //Jump - King Me
                    if (s == 0 && type == CheckerPiece.RedReg)
                    {
                        jump.edit(s, t, CheckerPiece.RedKing);
                        type = CheckerPiece.RedKing;
                    }
                    else if (s == 7 && type == CheckerPiece.BlackReg)
                    {
                        jump.edit(s, t, CheckerPiece.BlackKing);
                        type = CheckerPiece.BlackKing;
                    }
                    root = checkDoubleJump(root, type, s, t);
                }
            }
            return jump;
        }
        
        /*
         * This methods recursively checks for Double Jump scenarios.
         */
        internal AIMove checkDoubleJump(AIMove root, CheckerPiece type, int i, int j)
        {
            CheckerPiece[,] board = root.getboard();

            if (type == CheckerPiece.RedReg)
            {
                if (checkRange(i - 1, j - 1))
                {
                    if (board[i - 1, j - 1] == CheckerPiece.BlackReg || board[i - 1, j - 1] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i - 2, j - 2))
                        {
                            if (board[i - 2, j - 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i - 1, j - 1, 0);
                                root.edit(i - 2, j - 2, CheckerPiece.RedReg);
                                if ((i - 2) == 0)
                                {
                                    root.edit(i - 2, j - 2, CheckerPiece.RedKing);
                                    root = checkDoubleJump(root, CheckerPiece.RedKing, i - 2, j - 2);
                                }
                                else
                                {
                                    root = checkDoubleJump(root, CheckerPiece.RedReg, i-2, j-2);
                                }
                            }
                        }
                    }
                }
                else if (checkRange(i - 1, j + 1))
                {
                    if (board[i - 1, j + 1] == CheckerPiece.BlackReg || board[i - 1, j + 1] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i - 2, j + 2))
                        {
                            if (board[i - 2, j + 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i - 1, j + 1, 0);
                                root.edit(i - 2, j + 2, CheckerPiece.RedReg);
                                if ((i - 2) == 0)
                                {
                                    root.edit(i - 2, j + 2, CheckerPiece.RedKing);
                                    root = checkDoubleJump(root, CheckerPiece.RedKing, i - 2, j + 2);
                                }
                                else
                                {
                                    root = checkDoubleJump(root, CheckerPiece.RedReg, i - 2, j + 2);
                                }
                            }
                        }
                    }
                }
            }
            else if (type == CheckerPiece.RedKing) 
            {
                if (checkRange(i - 1, j - 1))
                {
                    if (board[i - 1, j - 1] == CheckerPiece.BlackReg || board[i - 1, j - 1] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i - 2, j - 2))
                        {
                            if (board[i - 2, j - 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i - 1, j - 1, 0);
                                root.edit(i - 2, j - 2, CheckerPiece.RedKing);
                                root = checkDoubleJump(root, type, i - 2, j - 2);
                            }
                        }
                    }
                }
                else if (checkRange(i - 1, j + 1))
                {
                    if (board[i - 1, j + 1] == CheckerPiece.BlackReg || board[i - 1, j + 1] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i - 2, j + 2))
                        {
                            if (board[i - 2, j + 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i - 1, j + 1, 0);
                                root.edit(i - 2, j + 2, CheckerPiece.RedKing);
                                root = checkDoubleJump(root, type, i - 2, j + 2);
                            }
                        }
                    }
                }
                else if (checkRange(i + 1, j - 1))
                {
                    if (board[i + 1, j - 1] == CheckerPiece.BlackReg || board[i + 1, j - 1] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i + 2, j - 2))
                        {
                            if (board[i + 2, j - 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i + 1, j - 1, 0);
                                root.edit(i + 2, j - 2, CheckerPiece.RedKing);
                                root = checkDoubleJump(root, type, i + 2, j - 2);
                            }
                        }
                    }
                }
                else if (checkRange(i + 1, j + 1))
                {
                    if (board[i + 1, j + 1] == CheckerPiece.BlackReg || board[i + 1, j + 1] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i + 2, j + 2))
                        {
                            if (board[i + 2, j + 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i + 1, j + 1, 0);
                                root.edit(i + 2, j + 2, CheckerPiece.RedKing);
                                root = checkDoubleJump(root, type, i + 2, j + 2);
                            }
                        }
                    }
                }
            }
            else if (type == CheckerPiece.BlackReg)
            {
                if (checkRange(i + 1, j - 1))
                {
                    if (board[i + 1, j - 1] == CheckerPiece.RedReg || board[i + 1, j - 1] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i + 2, j - 2))
                        {
                            if (board[i + 2, j - 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i + 1, j - 1, 0);
                                root.edit(i + 2, j - 2, CheckerPiece.BlackReg);
                                if ((i + 2) == 7)
                                {
                                    root.edit(i + 2, j - 2, CheckerPiece.BlackKing);
                                    root = checkDoubleJump(root, CheckerPiece.BlackKing, i + 2, j - 2);
                                }
                                else
                                {
                                    root = checkDoubleJump(root, CheckerPiece.BlackReg, i + 2, j - 2);
                                }
                            }
                        }
                    }
                }
                else if (checkRange(i + 1, j + 1))
                {
                    if (board[i + 1, j + 1] == CheckerPiece.RedReg || board[i + 1, j + 1] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i + 2, j + 2))
                        {
                            if (board[i + 2, j + 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i + 1, j + 1, 0);
                                root.edit(i + 2, j + 2, CheckerPiece.BlackReg);
                                if ((i + 2) == 7)
                                {
                                    root.edit(i + 2, j + 2, CheckerPiece.BlackKing);
                                    root = checkDoubleJump(root, CheckerPiece.BlackKing, i + 2, j + 2);
                                }
                                else
                                {
                                    root = checkDoubleJump(root, CheckerPiece.BlackReg, i + 2, j + 2);
                                }
                            }
                        }
                    }
                }
            }

            else if (type == CheckerPiece.BlackKing)
            {
                if (checkRange(i - 1, j - 1))
                {
                    if (board[i - 1, j - 1] == CheckerPiece.RedReg || board[i - 1, j - 1] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i - 2, j - 2))
                        {
                            if (board[i - 2, j - 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i - 1, j - 1, 0);
                                root.edit(i - 2, j - 2, CheckerPiece.BlackKing);
                                root = checkDoubleJump(root, type, i - 2, j - 2);
                            }
                        }
                    }
                }
                else if (checkRange(i - 1, j + 1))
                {
                    if (board[i - 1, j + 1] == CheckerPiece.RedReg || board[i - 1, j + 1] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i - 2, j + 2))
                        {
                            if (board[i - 2, j + 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i - 1, j + 1, 0);
                                root.edit(i - 2, j + 2, CheckerPiece.BlackKing);
                                root = checkDoubleJump(root, type, i - 2, j + 2);
                            }
                        }
                    }
                }
                else if (checkRange(i + 1, j - 1))
                {
                    if (board[i + 1, j - 1] == CheckerPiece.RedReg || board[i + 1, j - 1] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i + 2, j - 2))
                        {
                            if (board[i + 2, j - 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i + 1, j - 1, 0);
                                root.edit(i + 2, j - 2, CheckerPiece.BlackKing);
                                root = checkDoubleJump(root, type, i + 2, j - 2);
                            }
                        }
                    }
                }
                else if (checkRange(i + 1, j + 1))
                {
                    if (board[i + 1, j + 1] == CheckerPiece.RedReg || board[i + 1, j + 1] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i + 2, j + 2))
                        {
                            if (board[i + 2, j + 2] == 0)
                            {
                                root.edit(i, j, 0);
                                root.edit(i + 1, j + 1, 0);
                                root.edit(i + 2, j + 2, CheckerPiece.BlackKing);
                                root = checkDoubleJump(root, type, i + 2, j + 2);
                            }
                        }
                    }
                }
            }

            return root;
        }

        /*
         * This method generates all possible moves for the Red player on the current gameboard.
         */
        internal ArrayList generateRedMoves(AIMove root)
        {
            ArrayList movelist = new ArrayList();
            AIMove rootC = root.DeepClone(root);

            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    CheckerPiece[,] board = (rootC.DeepClone(rootC)).getboard();
                    if (board[i, j] == CheckerPiece.RedReg)
                    {
                        if (checkRange(i - 1, j - 1))
                        {
                            if (board[i - 1, j - 1] == 0)
                            {

                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i - 1, j - 1, CheckerPiece.RedReg);

                                //King Me
                                if ((i-1) == 0)
                                {
                                    slide.edit(i - 1, j - 1, CheckerPiece.RedKing);
                                }
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i - 1, j - 1] == CheckerPiece.BlackReg || board[i - 1, j - 1] == CheckerPiece.BlackKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.RedReg, i, j, i - 1, j - 1, i - 2, j - 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i - 1, j + 1))
                        {
                            if (board[i - 1, j + 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i - 1, j + 1, CheckerPiece.RedReg);

                                //King Me
                                if ((i-1) == 0)
                                {
                                    slide.edit(i - 1, j + 1, CheckerPiece.RedKing);
                                }
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i - 1, j + 1] == CheckerPiece.BlackReg || board[i - 1, j + 1] == CheckerPiece.BlackKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.RedReg, i, j, i - 1, j + 1, i - 2, j + 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                    }
                    else if (board[i, j] == CheckerPiece.RedKing)
                    {
                        if (checkRange(i - 1, j - 1))
                        {
                            if (board[i - 1, j - 1] == 0)
                            {

                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i - 1, j - 1, CheckerPiece.RedKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i - 1, j - 1] == CheckerPiece.BlackReg || board[i - 1, j - 1] == CheckerPiece.BlackKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.RedKing, i, j, i - 1, j - 1, i - 2, j - 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i - 1, j + 1))
                        {
                            if (board[i - 1, j + 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i - 1, j + 1, CheckerPiece.RedKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i - 1, j + 1] == CheckerPiece.BlackReg || board[i - 1, j + 1] == CheckerPiece.BlackKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.RedKing, i, j, i - 1, j + 1, i - 2, j + 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i + 1, j - 1))
                        {
                            if (board[i + 1, j - 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i + 1, j - 1, CheckerPiece.RedKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i + 1, j - 1] == CheckerPiece.BlackReg || board[i + 1, j - 1] == CheckerPiece.BlackKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.RedKing, i, j, i + 1, j - 1, i + 2, j - 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i + 1, j + 1))
                        {
                            if (board[i + 1, j + 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i + 1, j + 1, CheckerPiece.RedKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i + 1, j + 1] == CheckerPiece.BlackReg || board[i + 1, j + 1] == CheckerPiece.BlackKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.RedKing, i, j, i + 1, j + 1, i + 2, j + 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                    }
                }
            }

            return movelist;
        }

        /*
         * This method generates all possible moves for the BLACK player on the current gameboard.
         */
        internal ArrayList generateBlackMoves(AIMove root)
        {
            ArrayList movelist = new ArrayList();
            AIMove rootC = root.DeepClone(root);

            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {

                    CheckerPiece[,] board = rootC.getboard();

                    if (board[i, j] == CheckerPiece.BlackReg)
                    {
                        if (checkRange(i + 1, j - 1))
                        {
                            if (board[i + 1, j - 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i + 1, j - 1, CheckerPiece.BlackReg);

                                //King Me
                                if ((i+1) == 7)
                                {
                                    slide.edit(i + 1, j - 1, CheckerPiece.BlackKing);
                                }
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i + 1, j - 1] == CheckerPiece.RedReg || board[i + 1, j - 1] == CheckerPiece.RedKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.BlackReg, i, j, i + 1, j - 1, i + 2, j - 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i + 1, j + 1))
                        {
                            if (board[i + 1, j + 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i + 1, j + 1, CheckerPiece.BlackReg);
                                //King Me
                                if ((i+1) == 7)
                                {
                                    slide.edit(i + 1, j + 1, CheckerPiece.BlackKing);
                                }
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i + 1, j + 1] == CheckerPiece.RedReg || board[i + 1, j + 1] == CheckerPiece.RedKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.BlackReg, i, j, i + 1, j + 1, i + 2, j + 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                    }
                    else if (board[i, j] == CheckerPiece.BlackKing)
                    {
                        if (checkRange(i - 1, j - 1))
                        {
                            if (board[i - 1, j - 1] == 0)
                            {

                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i - 1, j - 1, CheckerPiece.BlackKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i - 1, j - 1] == CheckerPiece.RedReg || board[i - 1, j - 1] == CheckerPiece.RedKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.BlackKing, i, j, i - 1, j - 1, i - 2, j - 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i - 1, j + 1))
                        {
                            if (board[i - 1, j + 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i - 1, j + 1, CheckerPiece.BlackKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i - 1, j + 1] == CheckerPiece.RedReg || board[i - 1, j + 1] == CheckerPiece.RedKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.BlackKing, i, j, i - 1, j + 1, i - 2, j + 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i + 1, j - 1))
                        {
                            if (board[i + 1, j - 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i + 1, j - 1, CheckerPiece.BlackKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i + 1, j - 1] == CheckerPiece.RedReg || board[i + 1, j - 1] == CheckerPiece.RedKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.BlackKing, i, j, i + 1, j - 1, i + 2, j - 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }
                        if (checkRange(i + 1, j + 1))
                        {
                            if (board[i + 1, j + 1] == 0)
                            {
                                AIMove slide = new AIMove(root.DeepClone(root));
                                slide.edit(i, j, 0);
                                slide.edit(i + 1, j + 1, CheckerPiece.BlackKing);
                                slide.evaluateBoard();
                                movelist.Add(slide);
                            }
                            else if (board[i + 1, j + 1] == CheckerPiece.RedReg || board[i + 1, j + 1] == CheckerPiece.RedKing)
                            {
                                AIMove jump = checkJump(root.DeepClone(root), CheckerPiece.BlackKing, i, j, i + 1, j + 1, i + 2, j + 2);
                                if (jump != null)
                                {
                                    jump.evaluateBoard();
                                    movelist.Add(jump);
                                }
                            }
                        }

                    }
                }
            }

            return movelist;
        }
    }

    /*
     * AIMove Class
     * The Data Structure that holds the next possible moves.
     * phv - Primary Heurisitic Value - Based on # of Red Pieces - # of Black Pieces
     * srhv - Secondary Red Heuristic Value - Based on the Position of Red Pieces on the board
     * sbhv - Secondary Black Heuristic Value - Based on the Position of Black Pieces on the board
     */
    [Serializable]
    class AIMove
    {
        //AIMove Class Variables
        private CheckerPiece[,] rootboard;
        private AIMove nextState;
        private AIMove prevState;
        private int redPieces;
        private int blackPieces;
        private int phv;
        private int srhv;
        private int sbhv;
        private int[,] boardvalues = {
											{0, 4, 0, 4, 0, 4, 0, 4},
											{4, 0, 3, 0, 3, 0, 3, 0},
											{0, 3, 0, 2, 0, 2, 0, 4},
											{4, 0, 2, 0, 1, 0, 3, 0},
											{0, 3, 0, 1, 0, 2, 0, 4},
											{4, 0, 2, 0, 2, 0, 3, 0},
											{0, 2, 0, 3, 0, 3, 0, 4},
											{4, 0, 4, 0, 4, 0, 4, 0}
											};

        //Constructor - Input gameboard
        public AIMove(CheckerPiece[,] board)
        {
            this.rootboard = new CheckerPiece[8, 8];
            this.nextState = null;
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    this.rootboard[i, j] = board[i, j];
                    if (rootboard[i, j] == CheckerPiece.RedReg || rootboard[i, j] == CheckerPiece.RedKing)
                    {
                        this.redPieces++;
                    }
                    else if (rootboard[i, j] == CheckerPiece.BlackReg || rootboard[i, j] == CheckerPiece.BlackKing)
                    {
                        this.blackPieces++;
                    }

                }
            }

            this.phv = 0;
            this.srhv = 0;
            this.sbhv = 0;
        }

        //Constructor - Input current AIMove root
        public AIMove(AIMove root)
        {
            this.rootboard = (root.DeepClone(root)).getboard();
            this.nextState = null;
            this.prevState = root;

            this.phv = 0;
            this.srhv = 0;
            this.sbhv = 0;

            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    if (rootboard[i, j] == CheckerPiece.RedReg || rootboard[i, j] == CheckerPiece.RedKing)
                    {
                        this.redPieces++;
                    }
                    else if (rootboard[i, j] == CheckerPiece.BlackReg || rootboard[i, j] == CheckerPiece.BlackKing)
                    {
                        this.blackPieces++;
                    }

                }
            }
        }

        /*
         * AIMove Class Methods
         */
        public void evaluateBoard()
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {

                    if (rootboard[i, j] == 0)
                    { //Empty Cell
                    }
                    else if (rootboard[i, j] == CheckerPiece.RedReg)
                    { //Red Regular
                        this.phv += 1;
                        this.srhv += boardvalues[i, j];
                    }
                    else if (rootboard[i, j] == CheckerPiece.BlackReg)
                    { //Black Regular
                        this.phv -= 1;
                        this.sbhv += boardvalues[i, j];
                    }
                    else if (rootboard[i, j] == CheckerPiece.RedKing)
                    { //Red King
                        this.phv += 2;
                        this.srhv += boardvalues[i, j];
                    }
                    else if (rootboard[i, j] == CheckerPiece.BlackKing)
                    { //Black King
                        this.phv -= 2;
                        this.sbhv += boardvalues[i, j];
                    }
                }
            }
        }

        public CheckerPiece[,] getboard()
        {
            return rootboard;
        }

        public void edit(int i, int j, CheckerPiece value)
        {
            this.rootboard[i, j] = value;
        }

        public int getPHV()
        {
            return phv;
        }

        public int getSRHV()
        {
            return srhv;
        }
        public int getSBHV()
        {
            return sbhv;
        }

        public int getRedPieces()
        {
            return redPieces;
        }

        public int getBlackPieces()
        {
            return blackPieces;
        }

        public void setPrevState(AIMove prev)
        {
            this.prevState = prev;
        }
        public AIMove getPrevState()
        {
            return prevState;
        }

        public void setNextState(AIMove next)
        {
            this.nextState = next;
        }
        public AIMove getNextState()
        {
            return nextState;
        }

        public void printboard()
        {

            Console.WriteLine();

            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    Console.Write(" " + rootboard[i, j] + " ");
                }
                Console.WriteLine();
            }
        }

        public void copyHValues(AIMove source)
        {
            this.phv = source.getPHV();
            this.sbhv = source.getSBHV();
            this.srhv = source.getSRHV();
        }

        //DeepClone creates a physical (Deep) copy of the object in memory.
        //This is used to avoid object reference pointer problems (aka, shallow copying).
        public AIMove DeepClone<AIMove>(AIMove obj)
        {
            using (var ms = new MemoryStream())
            {
                var formatter = new BinaryFormatter();
                formatter.Serialize(ms, obj);
                ms.Position = 0;

                return (AIMove)formatter.Deserialize(ms);
            }

        }
    }
}

